package com.zfl;

import java.util.LinkedList;

public class MaximalRectangle {

    public int maximalRectangle(char[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;

        int[ ] heights = new int[col];
        int maxArea   = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                heights[j] = matrix[i][j]=='1'? heights[j]+1: 0;
            }
            maxArea = Math.max(maxArea,this.getLargestArea(heights));
        }
        return maxArea;
    }

    private int getLargestArea(int[] heights) {

        int maxArea=0;
        LinkedList<Integer> stack = new LinkedList<>();
        int n=heights.length;

        for (int i = 0; i <= n; i++) {
            int currrentHeight = i==n?0:heights[i];

            while(!stack.isEmpty()&&currrentHeight<heights[stack.peek()]) {
                int height = heights[stack.pop()];
                int left = stack.isEmpty()?-1:stack.peek();
                int right=i;
                int board = right-left-1;
                int currentArea = board*height;
                maxArea = Math.max(currentArea,maxArea);
            }
            stack.push(i);
        }
        return maxArea;
    }
}
